Міністерство освіти та науки України
Національний університет „Львівська політехніка”
кафедра ЕОМ
Лабораторна робота №3
з курсу: „Алгоритми і засоби цифрової обробки сигналів”
Тема: Швидкі алгоритми обчислення дискретних тригонометричних перетворень
Львів – 2004 р.
Мета роботи: Дослідити швидкі алгоритми дискретних тригонометричних перетворень і порівняти їх з алгоритмами безпосереднього обчислення тpигонометpних перетворень.
№
Завдання
9
Розробити процедуру дискретного тригонометричного перетворення вхідної послідовності x(n), розмірності N використовуючи алгоритм Algorithm. Формулу розкладу отримати за методом Кулі-Тьюкі.
Algorithm : ШПХ2 (швидке переотворення Хартлі заосновою 2) з прорідженням за часом.
N = 512
x(n) = ; n = 0, 1, ..., N-1.
Теоретичні відомості
Алгоритми швидкого перетворення Фур’є (ШПФ) можуть бути отримані за допомогою послідовного застосування операції розкладу одномірного масиву вхідних відліків сигналу на двохмірний. Ця операція здійснена тільки у випадку, коли N (довжина послідовності) є складним числом (N = N1 ( N2 ( ... ( Nj). Якщо N просте, його неможливо розкласти на прості співмножники; для такої послідовності алгоритмів ШПФ не існує. В більшості практичних випадків вхідну послідовність штучно продовжують додаванням нульових відліків до отримання N як складного числа.
Для характеристики розкладу використовують поняття “основа”, якщо всі співмножники однакові (N1 = N2 = ... = Nj) і “рощеплена основа”, якщо співмножники неоднакові.
Приклад. N = 64 = 2 ( 2 ( 2 ( 2 ( 2 ( 2 - основа 2.
N = 64 = 4 ( 4 ( 4 - основа 4.
N = 128 = 2 ( 4 ( 4 ( 4 - рощеплена основа 2-4.
Дискретне перетворення Хартлі
Дискретне перетворення Хартлі (ДПХ) кінцевої N-точкової послідовності x(n), n=0,1,...,N-1, N=2m m=1,2,3,..., т.е. - H(k) = ДПХN{x(n)}, визначається як
k = 0,1,...,N-1,
де , .
Алгоритм БПХ2 з прорідженням в часі. Позначимо через H1(k) і H2(k) ДПХ парних і непарних членів послідовності x(n): H1(k) = ДПХN/2{x(2n)} і H2(k) = ДПХN/2{x(2n+1)}.
Застосовуючи методику аналогічну як і при побудові алгоритмів ШПФ і виконавши відповідні перетворення отримаємо процедуру для розкладу алгоритмів БПХ.
H(k) = H1(k) + a; H(k+N/2) = H1(k) - a;
H(N/2-k) = H1(N/2-k) + b; H(N-k) = H1(N/2-k) - b;
; .
де k = 0,1,...,N/4-1;
Розклад необхідно проводити до тих пір поки H1(k) і H2(k) не будуть двухточковими ДПХ.
Алгоритм ШПХ2 з прорідженням по частоті. Загальна формула розкладу алгоритму з прорідженням по частоті задається виразами:
H(2k) = H1(k); H(2k+1) = H2(k), k=0,...,N/2-1
де H1(k), H2(k) - N/2-точкові ДПХ послідовностів x1(n), x2(n); x1(n) = x(n) +x(n+N/2), , n = 0,1,...,N/2-1.
На основі цього запишемо процедуру переходу до перетворень меншої розмірності в N-точковому алгоритмі ШПХ2:
a = x(n) - x(n+N/2); b = x(N/2-n) - x(N-n);
x1(n) = x(n) + x(n+N/2); x1(N/2-n)= x(N/2-n) + x(N-n);
,
n = 1, 2, ...,N/4-1.
Продовжуючи на основі цієї процедури розбиття отриманих послідовностей менших розмірностів до двохточкових, синтезуємо алгоритм ШПХ2 з прорідженням по частоті.
Комбінуючи формули розкладу алгоритмів БПХ за основою два і чотири з прорідженням в часі, отримаємо формули розкладу алгоритму за “рощепленою основою” 2-4 (БПХ24)
,
де H0(k) = ДПХN/2{x(2n)}, Hl(k) = ДПХN/4{xl(n)}, xl(n) = x(4n+l), l=1,3.
При переході до перетворень меншої розмірності використаємо процедуру:
a13 = H1(0) + H3(0); a31 = H1(0) - H3(0);
d1 = .H1(N/8); d3 = .H3(N/8);
H(0) = H0(0) + a13; H(N/4) = H0(N/4) + a31;
H(N/2) = H0(0) - a13; H(3N/4) = H0(N/4) - a31;
H(N/8) = H0(N/8) + d1; H(3N/8) = H0(3N/8) + d3;
H(5N/8) = H0(N/8) - d1; H(7N/8) = H0(3N/8) - d3;
;
; l=1,3;
a13 = a1 + a3; a31 = a1 - a3; b13 = b1 + b3; b31 = b3- b1;
H(k) = H0(k) + a13; H(N/4-k) = H0(N/4-k) + a31;
H(k+N/4) = H0(k+N/4) + b31; H(N/2-k) = H0(N/2-k) + b13;
H(k+N/2) = H0(k) - a13; H(3N/4-k) = H0(N/4-k) - a31;
H(k+3N/4) = H0(k+N/4) - b31; H(N-k) = H0(N/2-k) - b13,
k=1,2...,N/8-1.
Продовжуючи процес розбиття ...
